// https://www.lintcode.com/problem/number-of-islands/description

// 法一：UF
class UnionFind {
public:
    int* father;
    int cnt;
    UnionFind(int n) {
        father = new int[n];
        for (int i = 0; i < n; ++i) {
            father[i] = i;
        }
        cnt = n;
    }
    int find(int x) { //注意路径压缩
        int j = x;
        while (father[j] != j) {
            j = father[j];
        }
        while (x != j) {
            int tmp = father[x];
            father[x] = j;
            x = tmp;
        }
        return j;
    }
    void connect(int a, int b) {
        int fa = find(a);
        int fb = find(b);
        // cnt--; 注意!原先不通才连
        if (fa != fb) {
            father[fa] = fb;
            cnt--;
        }
    }
    int check() {
        return cnt;
    }
};

class Solution {
public:
    /**
     * @param grid: a boolean 2D matrix
     * @return: an integer
     */
    int numIslands(vector<vector<bool>> &grid) {
        if (grid.empty()) return 0;
        int n = grid.size();
        int m = grid[0].size();
        int water_cnt = 0;
        UnionFind uni(n * m);
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (grid[i][j]) {
                    if (i + 1 < n && grid[i + 1][j]) {
                        // uni.connect(n * i + j, n * (i + 1) + j);
                        uni.connect(m * i + j, m * (i + 1) + j);
                    }
                    if (j + 1 < m && grid[i][j + 1]) {
                        // uni.connect(n * i + j, n * i + j + 1);
                        uni.connect(m * i + j, m * i + j + 1);
                    }
                } else {
                    water_cnt++;
                }
            }
        }
        return uni.check() - water_cnt;
    }
};


// 个
class UnionFind {
public:
    int* father;
    int cnt = 0;
    UnionFind(int n) {
        father = new int[n];
        for (int i = 0; i < n; ++i) {
            father[i] = -1;
        }
    }
    void insert(int n) {
        father[n] = n;
        ++cnt;
    }
    int find(int x) {
        int j = x;
        while (father[j] != j) {
            j = father[j];
        }
        while (x != j) {
            int tmp = father[x];
            father[x] = j;
            x = tmp;
        }
        return j;
    }
    void connect(int a, int b) {
        int fa = find(a);
        int fb = find(b);
        if (fa != fb) {
            father[fa] = fb;
            cnt--;
        }
    }
    int get() {
        return cnt;
    } 
};
class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int n = grid.size();
        int m = grid[0].size();
        UnionFind uf(n * m);
        vector<int> dx = {1, 0, -1, 0};
        vector<int> dy = {0, 1, 0, -1};
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (grid[i][j] == '1') {
                    int node = i * m + j;
                    uf.insert(node);
                }
            }
        }
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (grid[i][j] == '1') {
                    int node = i * m + j;
                    // grid[i][j] = '0'; 不需要，最后的cnt是全局的，重复处理也没事
                    for (int d = 0; d < 4; ++d) {
                        int newNode = (i + dx[d]) * m + j + dy[d];
                        if (i + dx[d] >= 0 && i + dx[d] < n && j + dy[d] >= 0 && j + dy[d] < m && grid[i + dx[d]][j + dy[d]] == '1') {
                            uf.connect(node, newNode);
                        }
                    }
                }
            }
        }
        return uf.get();      
    }
};


// 法二：BFS
class Solution {
public:
    int numIslands(vector<vector<bool>> &grid) {
        queue<pair<int, int>> q;
        int cnt = 0;
        vector<int> dx = {1, 0, -1, 0};
        vector<int> dy = {0, 1, 0, -1};
        for (int i = 0; i < grid.size(); ++i) {
            for (int j = 0; j < grid[i].size(); ++j) {
                if (grid[i][j]) {
                    q.emplace(i, j);
                    cnt++;
                    grid[i][j] = 0;
                }
                while (!q.empty()) {
                    int x, y;
                    tie(x, y) = q.front();
                    q.pop();
                    for (int d = 0; d < 4; ++d) {
                        if (x + dx[d] < grid.size() && y + dy[d] < grid[0].size() && grid[x + dx[d]][y + dy[d]]) {
                                q.emplace(x + dx[d], y + dy[d]);
                                grid[x + dx[d]][y + dy[d]] = 0;
                        }
                    }
                }
            }
        }
        return cnt;
    }
};

// 法三：DFS
class Solution {
public:
    void dfs(vector<vector<bool>> &grid, int x, int y) {
        if (x < 0 || x >= grid.size()) return;
        if (y < 0 || y >= grid[0].size()) return;
        if (!grid[x][y]) return;
        grid[x][y] = false;
        dfs(grid, x + 1, y);
        dfs(grid, x - 1, y);
        dfs(grid, x, y + 1);
        dfs(grid, x, y - 1);
    }
    int numIslands(vector<vector<bool>>& grid) {
        // Write your code here
        if (grid.empty() || grid[0].empty()) return 0;
        int N = grid.size(), M = grid[0].size();
        int cnt = 0;
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < M; ++j) {
                if (grid[i][j]) {
                    dfs(grid, i, j);
                    ++cnt;
                }
            }
        }
        return cnt;
    }
};